package com.example.javamaday.list;

/**
 * 约瑟夫环测试
 */
public class JosephTest {

    public static void main(String[] args) {

        Node<Integer> head = null;
        Node<Integer> pre = null;

        // 创建41人的单向循环链表
        for (int i = 1; i <= 41; i++) {
            if (i == 1) {
                head = new Node<>(i, null);
                pre = head;
                continue;
            }
            // 如果不是第一个结点
            Node<Integer> newNodes = new Node<>(i, null);
            pre.next = newNodes;
            pre = newNodes;
            if (i == 41) {
                pre.next = head;
            }
        }
        int count = 0;
        Node n = head;
        Node before = null;
        while (n != n.next) {
            count++;
            if (count == 3) {
                before.next = n.next;
                System.out.print(n.item + ",");
                count = 0;
                n = n.next;
            } else {
                before = n;
                n = n.next;
            }
        }
        System.out.print("" + n.item);
    }

    private static class Node<T> {  //结点类
        T item;    //存储数据
        Node next; //下一个结点
        Node(T item, Node next) {
            this.item = item;
            this.next = next;
        }
    }
}
